// 2025/4/6
// https://leetcode.cn/problems/copy-list-with-random-pointer/description/?envType=study-plan-v2&envId=top-100-liked
// 随机链表的复制

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
    public:
        Node* copyRandomList(Node* head) {
            unordered_map<Node*, Node*> mp = {{nullptr, nullptr}};
            Node* cur = head;
            while(cur)
            {
                mp[cur] = new Node(cur->val);
                cur = cur->next;
            }
            cur = head;
            while(cur)
            {
                mp[cur]->next = mp[cur->next];
                mp[cur]->random = mp[cur->random];
                cur = cur->next;
            }
            return mp[head];
        }
    };